package com.hanxiaozhang.tree;

/**
 * 〈一句话功能简述〉<br>
 * 〈前缀树1版本〉
 *
 * @author hanxinghua
 * @create 2021/9/15
 * @since 1.0.0
 */
public class PrefixTree1 {

    public static void main(String[] args) {
        char a = 'a';
        char b = 'b';
        System.out.println(a);
        System.out.println((int) a);
        System.out.println(b);
        System.out.println((int) b);
        System.out.println("---------------");
        Tree tree = new Tree();
        tree.insert("abc");
        tree.insert("abcf");
        tree.insert("abca");
        tree.insert("abcc");
        tree.insert("add");
        tree.insert("abed");
        tree.insert("abc");
        System.out.println("abc search number is "+tree.search("abc"));
        System.out.println("abc prefixNumber is "+tree.prefixNumber("abc"));
        tree.delete("abc");
        System.out.println("abc search number is "+tree.search("abc"));
        System.out.println("abc prefixNumber is "+tree.prefixNumber("abc"));


    }


    /**
     * 节点
     * 假设字符串都是小写字符串，所以最多有26路，
     * 即创建一个26大小的数组
     */
    public static class Node {

        /**
         * 记录有多少个字符串通过该节点
         */
        public int pass;

        /**
         * 记录有多少个字符串截止到该节点
         */
        public int end;

        /**
         * 该节点有多少条路
         */
        public Node[] nexts;

        public Node() {
            pass = 0;
            end = 0;
            // 0 a
            // 1 b
            // ... ...
            // 25 z
            // nexts[i] ==null i方向上不存在
            // nexts[i] !=null i方向上存在
            nexts = new Node[26];
        }
    }


    public static class Tree {
        private Node root;

        public Tree() {
            root = new Node();
        }

        /**
         * 插入字符串
         *
         * @param word
         */
        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            Node node = root;
            node.pass++;
            int index = 0;
            // 从左往右遍历字符
            for (int i = 0; i < chs.length; i++) {
                // 由字符，对应成走向哪条路
                index = chs[i] - 'a';
                // 如果该节点不存这条路，创建
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                // 获取该节点
                node = node.nexts[index];
                // pass++
                node.pass++;
            }
            // end++
            node.end++;
        }

        /**
         * 删除
         *
         * @param word
         */
        public void delete(String word) {
            // search存在再删除
            if (search(word) != 0) {
                char[] chs = word.toCharArray();
                Node node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chs.length; i++) {
                    index = chs[i] - 'a';
                    // 如果 --node.nexts[index].pass == 0，
                    // 直接把当前节点的next[index]设置为null，让JVM回收
                    if (--node.nexts[index].pass == 0) {
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }

        /**
         * word这个单词之前加入过几次
         *
         * @param word
         * @return
         */
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node node = root;
            int index = 0;
            // 循环寻找
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }


        /**
         * 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
         *
         * @param pre
         * @return
         */
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node node = root;
            int index = 0;
            // 循环寻找
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }


}
